public class MaxProfit {
    // 买卖股票的最佳时机1
    // https://www.nowcoder.com/practice/64b4262d4e6d4f6181cd45446a5821ec?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public int maxProfit (int[] prices) {
        // write code here
        int len = prices.length;
        // f[i]表示第i天处于买入状态时候的最大利益
        int[] f = new int[len];
        // g[i]表示第i天处于卖出状态时候的最大利益
        int[] g = new int[len];
        //状态转移方程：
        // 因为只能买入卖出一次，所以是无法从卖出状态转换为买入状态的
        // 所以买入第i天买入状态的最大利益，只有是前一天处于买入状态或者是当太买入的
        // f[i] = max(f[i-1], -prices[i])
        // g[i] = max(g[i-1], f[i-1] + prices[i])
        f[0] = -prices[0];
        for (int i = 1; i < len; i++) {
            f[i] = Math.max(f[i-1], -prices[i]);
            g[i] = Math.max(g[i-1], f[i-1] + prices[i]);
        }
        return g[len-1];
    }
}
